//! https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
//! 剑指 Offer 42. 连续子数组的最大和
//! 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。
//! 求所有子数组的和的最大值。
//! 要求时间复杂度为O(n)。

pub struct Solution {}

#[allow(dead_code)]
impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut sum = 0;
        let mut ans = std::i32::MIN;
        nums.iter().for_each(|&x| {
            if sum < 0 {
                sum = x;
            } else {
                sum = sum + x;
            }

            ans = ans.max(sum);
        });
        ans
    }
    pub fn max_sub_array2(nums: Vec<i32>) -> i32 {
        let (mut tmp, mut max) = (0, -23333);
        for num in nums {
            if tmp < 0 {
                tmp = 0
            }
            tmp += num;
            if max < tmp {
                max = tmp
            }
        }
        max
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(
            Solution::max_sub_array(vec![-2, 1, -3, 4, -1, 2, 1, -5, 4]),
            6
        )
    }
}
